//求二叉树的所有路径，就是根节点到叶节点的所有路径
//可以采用递归加回溯算法（也算是回溯的一些引入了）
//回溯的时候要注意回溯要和递归永远在一起
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};
//采用前序遍历的方法进行求路径，这样方便父节点指向子节点
#include <vector>
#include <string>
using std::string;
using std::to_string;//将数字转化为字符串
using std::vector;
void traversal(TreeNode* cur,vector<int>& path,vector<string>& result)
{
    path.push_back(cur->val);

    //遇到叶子节点就进行操作，而不是直到空节点
    //这样可以控制空节点不进入递归循环，不会把空节点放入path
    if(!cur->left&&!cur->right) 
    {
        string sPath;
        for(int i=0;i<path.size();i++)
        {
            sPath+=to_string(path[i]);
            sPath+="->";
        }
        sPath+=to_string(path[path.size()-1]);
        result.push_back(sPath);
        return;
    }


    //回溯的部分         
    if(cur->left){
        traversal(cur->left,path,result);
        path.pop_back(); 
    }

    //回溯要和递归在一起
    if(cur->right){
        traversal(cur->right,path,result);
        path.pop_back();
    }
    //每次进行遍历后，弹出当前path的一个元素，然后从当前path开始遍历另一条路径
    
    //从递归栈来看，是从叶子节点一步步向上回溯
}

vector<string> binaryTreePaths(TreeNode* root)
{
    vector<int> path;
    vector<string> result;
    if(!root) return result;
    traversal(root,path,result);
    return result;
}




//迭代法，其实就是使用栈实现二叉树的前序遍历
//使用一个栈存储要遍历的节点，一个栈存储路径，一个vector存储结构
#include <stack>
using std::stack;
vector<string> binaryTreePaths_stack(TreeNode* root)
{
    stack<TreeNode*> treest;
    stack<string> pathst;
    vector<string> result;
    if(!root) return result;
    treest.push(root);
    pathst.push(to_string(root->val));
    while (!treest.empty())
    {
        //注意每次栈操作节点和path都是一起进行，这样保证了每个节点与当前的path都是对应的
        TreeNode* node=treest.top(); treest.pop();
        string path=pathst.top(); pathst.pop();

        if(!node->left&&!node->right) //叶子节点
            result.push_back(path);


        //先入栈右节点，再入栈左节点，使顺序为中左右
        if(node->right)
        {
            treest.push(node->right);
            pathst.push(path+"->"+to_string(node->right->val));
        }
        if(node->left)
        {
            treest.push(node->left);
            pathst.push(path+"->"+to_string(node->left->val));
        }
    }
    return result;
    
}